package leetcode.dp;

import java.util.Arrays;
import java.util.Currency;

public class LengthOfLis {
    public static void main(String[] args) {
        int[] nums = {4,10,4,3,8,9};
        System.out.println(process(nums));
        System.out.println(process2(nums));
    }

    public static int process(int[] nums){
        if (nums == null){
            return 0;
        }
        return process(nums,0,1);
    }

    public static int process(int[] nums,int i,int max){
        if (nums.length-1 <= i){
            return 1;
        }
       if (nums[i] < nums[i+1]){
           return max+process(nums,i+1,max);
       } else {
           return process(nums,i+1,max);
       }
    }
    
    public static int process2(int[] nums){
        int len = nums.length-1;
        int[] ans = new int[len+1];
        Arrays.fill(ans,1);
        int max = -1;
        int pre = len;
        for (int i = 1; i <=len; i++) {
            if (nums[len -i] < nums[len-i+1]){
                if (nums[len-i+1] >= nums[pre]){
                    ans[i] = Math.max(ans[i-1],1);
                }
                ans[i] = Math.max(ans[i-1],max)+ans[i];
            } else {
                ans[i] = Math.max(max,ans[i]);
            }
            max = Math.max(ans[i],max);
        }
        return ans[len];
    }
}
